package com.zyk.leetcode;

import com.zyk.util.TreeUtil;

/**
 * @author zhangsan
 * @date 2021/4/9 17:06
 */
public class M0412 {

    // https://leetcode-cn.com/problems/paths-with-sum-lcci/
    public int pathSum(TreeNode root, int sum) {
        preProcess(root, sum);
        return ans;
    }

    public void preProcess(TreeNode root, int sum) {
        if (root == null)
            return;
        process(root, sum - root.val);
        preProcess(root.left, sum);
        preProcess(root.right, sum);
    }
    int ans;

    public void process(TreeNode root, int rest) {
        if (rest == 0)
            ans++;
        if (root == null)
            return;
        if (root.left != null)
            process(root.left, rest - root.left.val);
        if (root.right != null)
            process(root.right, rest - root.right.val);
    }


    // for test
    public static void main(String[] args) {
        /*Integer[] treeInfo = {
                5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, null, 5, 1
        };
        int target = 22;*/
        Integer[] treeInfo = {1, 2};
        int target = 2;
        TreeNode root = TreeUtil.generateTreeByArr(treeInfo);


        M0412 test = new M0412();
        System.out.println(test.pathSum(root, target));
    }

}
